package a3;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;
import useful.*;

public class EdmondKarp extends FordFulkerson{
    @Override
    protected List<String> ChoosePath(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, Bijective<String,Integer> cityMap, double[][] currentFlowMatrix, String q, String s) {
        Set<String> visited = new HashSet<>();
		Queue<Pair<String,List<String>>> vertexQueue = new PriorityQueue<>();
		List<String> result = new ArrayList<>();
		
		vertexQueue.add(new Pair(q, new ArrayList<>()));
		result.add(q);
		visited.add(q);
		
		while(!vertexQueue.isEmpty()) {
			Pair<String,List<String>> current = vertexQueue.poll();
			List<String> way = current.second();
			String currentVertex = current.first();
			way.add(currentVertex);
			
			for(DefaultWeightedEdge edge : graph.outgoingEdgesOf(currentVertex)) {
				++accessCount;
				String targetVertex = graph.getEdgeTarget(edge);
				if (targetVertex.equals(s) && currentFlowMatrix[cityMap.second(currentVertex)][cityMap.second(s)] < graph.getEdgeWeight(edge)) {
					result = way;
					break;
				} else {
					if (!visited.contains(targetVertex) && currentFlowMatrix[cityMap.second(currentVertex)][cityMap.second(targetVertex)] < graph.getEdgeWeight(edge))  {
						vertexQueue.add(new Pair(targetVertex, new ArrayList<>(way)));						
						visited.add(targetVertex);
					}
				} 					
			}
			
			for(DefaultWeightedEdge edge : graph.incomingEdgesOf(currentVertex)) {
				++accessCount;
				String targetVertex = graph.getEdgeSource(edge);
				if (targetVertex.equals(s)) {
					result = way;
					break;
				} else {
					if (!visited.contains(targetVertex) && currentFlowMatrix[cityMap.second(targetVertex)][cityMap.second(currentVertex)] > 0)  {
						vertexQueue.add(new Pair(targetVertex, new ArrayList<>(way)));						
						visited.add(targetVertex);
					}
				} 					
			}
		
		}	
		if (result.size() > 1) {//Es gibt einen vergrößernden Weg
			result.add(s);
			System.out.print(result);
		} else 
			return null;
		return result;
    }
}
